Implementations of the claimed invention generally may relate to schemes for data compression and, more particularly, to such schemes that involve run length encoding.
Run Length Encoding (RLE) has been used for data compression for many years. Because RLE use the repetition of data elements to compress the data, it works very well on images displayed on TVs and computers. For example, within a black and white graphical image, there may be significant repetition of pixels, especially the white pixels. Hence, for such an image, one may use RLE to compress the data in the frame buffer holding this image and reduce, for example, the memory size, power and/or bandwidth requirements of such a buffer.
One known design issue with RLE is that it is possible for the RLE process to expand the size or amount of data, instead of compress it. This issue arises in RLE by virtue of the observation that it takes more than one data element (e.g., at least a pair of data elements) to describe both 1) the data level or value and 2) it run length. This pair of data elements may sometimes be referred to as a “command pair.” If too many changes occur within the data to be run length encoded, then it may take a greater number of data elements (e.g., command pairs) to describe the run-length and value pairs than the number of data elements originally contained in the data. Such a larger amount of data after RLE may be referred to as “data expansion.”
Because of the possibility of this data expansion, system and circuit designers may typically design systems in view of the “worst case” amount of data expansion. Such design practices may reduce or eliminate the use of RLE, for some applications, because the “worst case” amount of data expansion may use more power, memory size and/or bandwidth than not employing RLE at all.